package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.List;

/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2022-04-02 11:05
 */
public class BL45跳跃游戏II {

    public static void main(String[] args) {

        int[] nums = {2, 3, 1, 1, 4};
        //使用list记录每次的代价
//        List<Integer> list = new ArrayList<>();
//        canJump2(nums, nums.length - 1, list);
//        System.out.println(list);
        System.out.println(canJump3(nums));
    }


    /**
     * I只记录了是否可以到达终点 却并不在意步数是否被浪费
     * <p>
     * II 跳跃数指的是经历数组下标的数量
     * ??即使第一步跳的是最大步数 也不能代表这是最少步数
     * ??怎么才能保证一定是最优路径里面的路线呢
     * <p>
     * 如果总是可以到达数组的最后一个位置？意思就是不管路线怎么选都能走到终点 则还是从终点开始 找到上一步跨越最大的步数即可
     * <p>
     * 优化：
     * 没必要每次都从起点开始遍历
     * 使用map记录能到达某节点的最佳节点
     *
     * 解法：
     * 从终点出发 记录能到达终点的每一个节点 前面的节点总能覆盖后面的节点(前面的节点优先级高于后面的节点)
     * 使用上面的逻辑不断遍历 直到到达起点
     *
     * 最后通过遍历后的数组 从终点出发,按照下标前进,直到到达起点
     *
     * @param nums
     * @return
     */
    public static void canJump2(int[] nums, int index, List<Integer> list) {
        //每次从起点遍历 找到到达n的最佳节点 离起点最近的即为最佳节点
        for (int i = 0; i < index; i++) {
            if (nums[i] >= index - i) {
                list.add(nums[i]);
                canJump2(nums, i, list);
                break;
            }
        }
    }


    /**
     * 使用数组存储能到达n的最小下标
     *
     * @param nums
     */
    public static int canJump3(int[] nums) {
        if(nums.length == 1){
            return 0;
        }
        int[] nums2 = new int[nums.length];
        //反向查找 赋值
        for (int i = nums.length - 2; i >= 0; i--) {
            if(nums[i] >0){
                int end  = Math.min(nums.length-1,i+nums[i]);
                for (int j = i; j <= end; j++) {
                    nums2[j] = i;
                }
            }
        }

        //得到num2之后只需要遍历 从n开始逐步跳跃直到值为0即可
        int total = 1;
        int index = nums.length - 1;
        while (nums2[index] != 0) {
            total++;
            index = nums2[index];
        }
        return total;
    }
}
